package 链表;

public class Demo09 {
    static class Solution {
        public ListNode partition(ListNode head, int x) {
            ListNode minNode = new ListNode(0);
            ListNode MaxNode = new ListNode(0);
            ListNode curmin = minNode;
            ListNode curMax = MaxNode;
            while (head != null) {
                if (head.val < x) {
                    curmin.next = head;
                    head = head.next;
                    curmin = curmin.next;
                } else {
                    curMax.next = head;
                    head = head.next;
                    curMax = curMax.next;
                    curMax.next = null;
                }
            }

            curmin.next = MaxNode.next;
            return minNode.next;
        }
    }
}
